Лемма о несамодвойственной функции

Пусть $f \notin S$. Тогда функции $0$ и $1$ можно задать формулами над множеством $\{f, \neg\}$.

Так как $f$ — $k$-местная несамодвойственная функция, то по определению существует набор, на котором значение функции совпадает со значением на противоположном наборе: $$\exists{\vec{b} = (b_{1}, \dots, b_{k}) \in \{0, 1\}^{k}}\mathpunct{:}~~ f(b_{1}, \dots, b_{k}) = f(\bar{b}_{1}, \dots, \bar{b}_{k})$$ Рассмотрим унарную функцию $\phi(x) = f(x^{b_{1}}, \dots, x^{b_{k}})$, где $x^{b_{i}}$ принимает значение $x$, если $b_{i}=1$, и $\bar{x}$, если $b_{i}=0$. Проверим значения функции: $$\phi(0) = f(\bar{b}_{1}, \dots, \bar{b}_{k}) = f(b_{1}, \dots, b_{k}) = \phi(1)$$ Так как $\phi(0) = \phi(1)$, то $\phi(x)$ — константа ($0$ или $1$). Вторую константу можно получить как $\overline{\phi(x)}$. Поскольку в конструкцию входят только $f$ и отрицания переменных, константы $0$ и $1$ выразимы формулами над $\{f, \neg\}$. $\square$